Dilation and erosion of images are operations commonly used in image analysis. Both of these operations depend on finding the maximum, or minimum, value of an input and assigning that value (the maximum or minimum value) to the output of the dilation or erosion within a pre-specified range.
Data input is received, and with that input is created a dilated, or eroded output. The dilated image is defined by assigning to each input datum the largest value of the data within a specified range. The eroded image is defined by assigning to each input datum the smallest value of the data within a specified range. For example, in applying a dilation of 8 to a specific image, the output is obtained by applying to each pixel the largest value of the 8 pixels in front of it. This may be expressed as:
for any given pixel Y,
let Y have the value of the maximum value of the selected from the group consisting of, Y, Y+1, Y+2, Y+3, Y+4, Y+5, Y+6, Y+7,
or simply:       y    i    =            max                        max          ⁢                                           ⁢          0                ≤        j        <        p              ⁢          x              i        +        j            
where yi is the output unit being dealt, xi is the input corresponding to the output datum yi, p is the specified number of data inputs, in this case 8, and j is all the values from 0 to p−1. Erosion is essentially the same as dilation, the only difference being that for erosion max is replaced by min.
A challenge is to find all the values of y, in the efficient manner. It is possible to obtain all the values for y with p comparisons per datum. One goes through all the datum and compares each datum with each of the p data in front of it, and for the output, uses the largest of those comparisons.
The Gil-Warner van Herk algorithm is a way to process the min and max values of a given input regardless of the value of p. There are 3 steps to the Gil-Werman van Herk Algorithm (hereafter referred to as GWVH):                1. Partitioning the data into overlapping segments of size 2p−1        2. Creating values Rk and Sk per datum per segment        3. Merging the Rk and Sk values to obtain the largest value per datum        
Partitioning the data:                The incoming data is partitioned into overlapping segments of size 2p−1, each segment centered at Xp−1, X2p−1, X3p−1 . . . ,. For example, if the incoming data consists of 41 data, and p is set to be 5, each segment is 9 data long (2*5)−1), and they would be centered at X4, X9, X14, X19, X24, X29, X34 and X39. That is to say, segment 1 starts at X0 and ranges through X8. Segment 2 starts at X5 and ranges through X13. Segment 3 starts at X10 and ranges through X18. Segment 4 starts at X15 and ranges through x23. Segment 5 starts at X20 and ranges through X28. Segment 6 starts at X25 and ranges through X33. Segment 7 starts at X30 and ranges through X38. Segment 8 starts at X35 and ranges through X40.        
Creating values Rk and Sk per datum per segment:
The GWVH algorithm starts at the center of each segment, and gives the center segment the Rk and Sk (in this case, R0 and S0, as the center k=0) of that segment. IE. Each center segment's Rk and Sk values are the values of that segment. Each datum is then given an Rk and Sk value as follows:                The Rk values:        for each value of k (Where k goes from 0 to p−1) the GWVH algorithm compares the value of the current Datum with the value of Rk−1 for that segment, and assigns Rk for the current datum to the larger of those two.        For example in the above case (41 datum numbered 0 . . . 40, p=5) looking at the third segment:                    k=0. The GWVH algorithm assigns Rk (in this instance R0, as k=0) for 14 to whatever 14 is (14 is the center of the third segment).            k=1. Then, the GWVH algorithm looks at datum 13, and compares the value of datum 13 to the value of Rk−1 for that segment (in this case R0 of the third segment) and assigns Rk for the current datum (In this case, R1 of the third segment) to the greater of the 2 values.            k=2, Then, the GWVH algorithm looks at datum 12, and compares the value of datum 12 to the value of Rk−1 for the segment (in this case, R1 of the third segment) and assigns Rk for the current datum (In this case, R2 of the third segment) to the greater of the 2 values.            k=3, Then, the GWVH algorithm looks at datum 11, and compares the value of datum 11 to the value of Rk−1 for that segment (in this case, R2 of the third segment) and assigns Rk for the current datum (In this case, R3 of the third segment) to the greater of the 2 values.                        
k=4, Then, the GWVH algorithm looks at datum 10, and compares the value of datum 10 to the value of Rk−1 for that segment (in this case R3 of the third segment) and assigns Rk for the current datum (In this case, R4 of the third segment) to the greater of the 2 values.                or, expressed more simply:Rk=max(Xj, Xj−1, . . . , Xj−k)        
where Xj is the center of each segment and k=0, . . . p−1.                The Sk values:        The Sk are computed the same way as the Rk values, except that as k increases you look at the higher values of datum, so in the third segment Sk where k=0 is still the value of datum 14, but Sk when k is one is the larger of datum 14, and datum 15. The equation for Sk is:Sk=max(Xj, Xj+1, . . . , Xj+k).        
Having generated an Rk and Sk for each datum, the GWVH algorithm proceeds to merge various Rk and Sk values to fine the max filter as follows:
The original definition for the max filter looks like:       y    i    =            max                        max          ⁢                                           ⁢          0                ≤        j        <        p              ⁢          x              i        +        j            
The algorithm substitutes max(Xj−k, Xj−(k−1), . . . Xj, Xj+1, . . . , Xj−p−k−1) for       max                  max        ⁢                                   ⁢        0            ≤      j      <      p        ⁢            x              i        +        j              .  
Considering the above substitution,       max                  max        ⁢                                   ⁢        0            ≤      j      <      p        ⁢      x          i      +      j      implies taking the largest value of any given X, from Xi through Xi+p−1. Considering the substitution max(Xj−k, Xj−(k−1), . . . Xj, Xj+1, . . . , Xj+p−k−1), start at Xj−k for arbitrary values of j and k. The algorithm is required find the max value from Xj−k through Xj−k+p−1, which is in fact what has been done. Having defined Rk and Sk over all the different segments, the algorithm must determine max(Xj−k, Xj−(k−1), . . . Xj, Xj+1, . . . , Xj+p−k−1) for a given j, and a given k. Having determined that the Rk between a current datum and the next center datum is the largest value between the current datum and the next center datum, the algorithm need no longer compare the current datum with any data other than the Rk of this datum until the next center datum. From the next center datum on, the Sk's remain the same or increase (are monotonically increasing), so to find the largest value from the next mid datum on, the GWVH algorithm chooses the correct Sk of the current segment, which is the datum p−1 away from the current datum, namely the datum Sp−k−1 of this segment, remembering that for any given segment S0 is the mid datum, therefore Sp is p away from the mid datum. The definition requires the output for any given datum to be the largest of itself and the p−1 data is front of it. The algorithm need not compare a datum p away, as it requires the largest of the current datum, and all the datum p−1 from it. Using the above definition the current datum is k behind the next mid datum, where k may be 0, so the algorithm uses the datum that is p−k−1 past the mid datum of the section that the current datum has an Rk value of, thus value of datum Sp−k−1. Once the GWVH algorithm has determined the Rk and Sk, there is one comparison to do to find the max value for any given datum, namely:                               y          i                =                ⁢                              max                                                                       ⁢                                                max                  ⁢                                                                           ⁢                  0                                ≤                j                <                p                                              ⁢                      x                          i              +              j                                                              =                ⁢                  max          ⁡                      (                                          x                                  j                  =                  k                                            ,                              x                                  j                  -                  k                  +                  1                                            ,                              …                ⁢                                                                   ⁢                                  x                  j                                            ,                              x                                  j                  +                  1                                            ,                              …                ⁢                                                                   ⁢                                  x                                      j                    +                    p                    -                    k                    -                    1                                                                        )                                                  =                ⁢                  max          ⁢                                    (                                                R                  k                                ,                                  s                                      p                    -                    k                    -                    1                                                              )                        .                              
The GWVH algorithm does 1 comparison per datum for each Rk and one comparison for each Sk. It then does one comparison for to determine the max over p for any given datum, giving a total of 3 comparisons per datum, regardless of the size of p. It should be noted that for the cases of k=0, and k=p−1 there is not need to do a comparison, one can simply choose the appropriate Rk or Sk, (k=0, Sk, k=p−1, Rk), without having to do the comparison.
In image analysis, it is often useful to take the opening, or the closing filter, that is, for the opening filter, filtering the data through a max filter, and then taking the output of the data, and running it through a min filter, or, for the closing filter, taking the data and running it through a min filter, and then taking the data and running it through a max filter. The above algorithm takes approximate 6 comparisons per data datum. Image analysis can be expensive in terms of computer time, and it is useful to find ways of shortening the amount of processing needed to do any given operation.